package leetcode;

import java.util.Arrays;

public class LeetCode134 {

    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;

        int total_tank = 0;
        int curr_tank = 0;
        int starting_station = 0;
        for (int i = 0; i < n; ++i) {
            total_tank += gas[i] - cost[i];
            curr_tank += gas[i] - cost[i];
            // If one couldn't get here,
            if (curr_tank < 0) {
                // Pick up the next station as the starting one.
                starting_station = i + 1;
                // Start with an empty tank.
                curr_tank = 0;
            }
        }
        return total_tank >= 0 ? starting_station : -1;
    }

    //当前油量+邮箱-消耗>0
    public int canCompleteCircuit1(int[] gas, int[] cost) {
        int sum = 0, n = gas.length, current = 0, walk;
        for (int i : cost) {
            sum += i;
        }
        //起点位置
        loop1:
        for (int i = 0; i < n; i++) {
            current = gas[i];
            walk = i;
            //步行步数
            for (int j = 0; j < n; j++) {
                if (walk < n - 1) {
                    current = current - cost[walk];
                    if (current < 0)
                        continue loop1;
                    current += gas[walk];
                    walk++;
                } else {
                    current = current - sum;
                    if (current < 0)
                        continue loop1;
                    current += gas[0];
                    walk = 1;
                }
            }
            return i;
        }
        return -1;
    }
//------------------------------------------------------------------
}
